package jm.algorithm.sort;

/**
 * @Description 基数排序
 * @date 2022/5/8 20:37
 */
public class RadixSort extends Sort<Integer>  {

    @Override
    protected void sort() {
        // 获取数组最大值
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }

        // 计算基数
            // 个位数 ： x / 1 % 10
            // 十位数 ： x / 10 % 10
            // 百位数 ： x / 100 % 10

        // 针对最大值的位数判断需要执行多少次计数排序
        for (int divider = 1; divider <= max; divider *= 10) {
            countingSort(divider);
        }
    }


    /**
     * 针对基数进行计数排序
     * @param divider 被除数
     */
    private void countingSort(int divider){
        int[] counts = new int[10];

        for (Integer integer : arr) {
            counts[integer / divider % 10]++;
        }

        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        int[] newArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = --counts[arr[i] / divider % 10];
            newArr[index] = arr[i];
        }

        for (int i = 0; i < newArr.length; i++) {
            arr[i] = newArr[i];
        }
    }

}
